package avl;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 08 - 20
 * Time:19:05
 */

/***
 * 1.AVL树定义： 搜索树+ 平衡树
 * 2.操作
 * （1）插入：普通搜索树插入——O(logn) + 调整平衡性（O(logn)） ——还是O(logn)
 * （2）查找：普通搜索树查找——O(logn)
 * （3）删除：——O(logn)
 * 3.如何进行AVL树的正确性验证？
 * （1）整棵树是一棵搜索树 <=> 中序遍历时有序的；
 * （2）整棵树是一棵平衡树 <=> 每个节点的bf 在{-1,0,1} && 每个节点的bf计算正确；
 */
public class AVLTree {
    public AVLNode root;
    public int size = 0;//保存树的节点个数

    /***
     *1.二叉平衡树的插入
     * @param key
     */
    public void  insert(long key){

        AVLNode node = new AVLNode();
        node.key = key;
        node.left = null;
        node.right = null;
        node.parent = null;
        node.bf = 0;

        if(root == null){
            root = node;
            size ++;
            return;
        }

        AVLNode current = root;
        AVLNode parent = null;
        while(current != null){
            if(key == current.key){
                return;
               // throw new RuntimeException("插入失败，key值重复" + key);
            }else if(key < current.key){
                parent = current;
                current = current.left;
            }else{
                parent = current;
                current = current.right;
            }
        }
        //插入操作
        node.parent = parent;
        if(key < parent.key){
            parent.left = node;
        }else{
            parent.right = node;
        }
        avlAdjust(parent,node);

        size++;
    }

    //插入节点的时候二叉平衡树的调整
    private void avlAdjust(AVLNode parent, AVLNode node) {
       //parent != null &&& node != null
        while(true){
           //进行平衡因子的调节
            if(node == parent.left){
                parent.bf ++;
            }else{
                parent.bf--;
            }

            //情况1：
            if(parent.bf == 0){
                return;
            }
            //情况2：
            if(parent.bf == -1 || parent.bf == 1){
                node = parent;
                parent = parent.parent;

                if(parent == null){
                    //向上走到根节点位置
                    return;
                }
                continue;
            }

            //情况3：parent.bf == -2 || parent .bf = 2
            break;
        }
        //走到这里，一定是出现失衡情况了
        if(parent.bf == 2){//左失衡
            if(node.bf == 1){//LL失衡——右旋parent即可
                rightRotate(parent);

                parent.bf = node.bf = 0;
            }else{//LR失衡 node.bf == -1——先左旋node，再右旋parent即可

                AVLNode c = node.right;
                int condition;
                if(parent.right == null){
                    condition = 1;
                }else if(c.bf == 1){
                    condition = 2;
                }else{
                    condition = 3;
                }
                leftRotate(node);//node是 b
                rightRotate(parent);//parent 是 a

                //调整平衡因子
                if(condition == 1){
                    parent.bf = node.bf = c.bf = 0;
                }else if(condition == 2){
                    parent.bf = -1;
                    node.bf = c.bf = 0;
                }else{
                    parent.bf = c.bf = 0;
                    node.bf = 1;
                }
            }
        }else{//右失衡 parent.bf == -2
            if(node.bf == -1){//RR失衡——左旋parent即可
                leftRotate(parent);

                parent.bf = node.bf = 0;

            }else{//RL 失衡  node.bf == 1
                AVLNode c = node.left;
                int condition;
                if(parent.left == null){
                    condition = 1;
                }else if(c.bf == 1){
                    condition = 2;
                }else{
                    condition = 3;
                }
                rightRotate(node);
                leftRotate(parent);

                if(condition == 1){
                    parent.bf = node.bf = 0;
                }else if(condition == 2){
                    parent.bf = c.bf = 0;
                    node.bf = -1;
                }else{
                    parent.bf = 1;
                    node.bf = c.bf = 0;
                }
            }
        }
    }

    /***
     * 以b节点进行左旋
     * @param b
     */
    private void  leftRotate(AVLNode b){

        //parent代表b节点可能存在的父节点
        AVLNode parent = b.parent;

        //图中的a节点
        AVLNode a = b.right;

        //leftOfRight代表图中的乙子树的根节点
        AVLNode leftOfRight = a.left;

        /***
         * 其中：m != null  && right != null
         * 但是parent 不能保证 ！null, leftOfRight 不保证 ！null
         */

        a.parent = parent;
        if(parent == null){
            //b == root
            root = a;
        }else{
            if(b == parent.left){
                parent.left = a;
            }else{
                parent.right = a;
            }
        }
        a.left = b;
        b.parent = a;

        b.right = leftOfRight;
        if(leftOfRight != null){
            leftOfRight.parent = b;
        }
    }
    /***
     * 以b节点进行右旋
     */

    private void rightRotate(AVLNode b){
        AVLNode parent = b.parent;
        AVLNode left = b.left;
        AVLNode rightOfLeft = left.right;

        left.parent = parent;
        if(parent == null){
            root = left;
        }else{
            if(b == parent.left){
                parent.left = left;
            }else{
                parent.right = left;
            }
        }
        left.right = b;
        b.parent = left;

        b.left = rightOfLeft;
        if(rightOfLeft  != null){
            rightOfLeft.parent = b;
        }
    }

    /***
     * 左旋单元测试
     * @param args
     */
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        AVLNode n5 = new AVLNode();
        n5.key = 5;

        AVLNode n6 = new AVLNode();
        n6.key = 6;

        AVLNode n7 = new AVLNode();
        n7.key = 7;

        n5.right = n6;
        n6.parent = n5;

        n6.right = n7;
        n7.parent = n6;

        tree.root = n5;
        tree.leftRotate(tree.root);
        System.out.println("Hello");
    }
}
